package com.sise.Linked;

/**
 *      160. 相交链表
 *
 *      给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 *      图示两个链表在节点 c1 开始相交：
 *      题目数据 保证 整个链式结构中不存在环。
 *      注意，函数返回结果后，链表必须 保持其原始结构 。
 *
 *      题解：
 *          https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/jiao-ni-yong-lang-man-de-fang-shi-zhao-dao-liang-2/
 *
 *          A走的路径：a + c + b
 *          B走的路径：b + c + a
 *
 *          当 a、b 走到结尾时，就反过来走另外一方的路，那么最终的相交点就是一样的。
 */
public class _160_getIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;                 // 这里将 headA 的位置赋给 a，然后用 a 进行移动，这里不能使用 headA 移动，否则会破坏原本的结构
        ListNode b = headB;

        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}